\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}
	
	\begin{itemize}
		\item
		最长公共子序列：\\
		\(f[i, j]=\left\{\begin{cases}{cc}0 & i=0 \text { or } \mathrm{j}=0 \\ f[i-1, j-1]+1 & i, j>0 \text { and } a_{i}=b_{j} \\ \max (f[i, j-1], f[i-1, j]) & i, j>0 \text { and } \mathrm{a}_{i} \neq b_{j}\end{cases}\right.\)
		\item
		最长公共子串：\\
		\(f[i, j]=\left\{\begin{cases}{cc}0 & i=0 \text { or } \mathrm{j}=0 \\ f[i-1, j-1]+1 & i, j>0 \text { and } a_{i}=b_{j} \\ 0 & i, j>0 \text { and } \mathrm{a}_{i} \neq b_{j}\end{cases}\right.\)
		\item
		\(LCS\) 转换为 \(LIS\)：\\
		需要满足：\(a,b\) 为排列或者 \(a,b\) 中出现的字母不重复时才可转换\\
		\(\begin{cases} A:3~2~1~4~5\\ B:1~2~3~4~5\end{cases} \rightarrow\)
		\(\begin{cases} A:a~b~c~d~e\\ B:c~b~a~d~e\end{cases}\)
		
		这样标号之后，\(LCS\) 长度显然不会改变，但是出现了一个性质：\\
		两个序列的子序列，一定是A的子序列，而A本身就是单调递增的，因此这个子序列是单调递增的。
		\item
		公共子序列个数：\\
		非种类数\\
		定义 \(f_{i,j}\) 表示 \(a\) 的前 \(i\) 位，\(b\) 的前 \(j\)
		位的公共子序列个数\\
		于是 \(f_{i,j} = f_{i-1,j} + f_{i,j-1}-f_{i-1,j-1}\)
		（想象一下二维前缀和）\\
		而当 \(a_i = b_j\) 时：\\
		\(\because a_i,b_j\) 可构成一个新的公共子序列，\(a_i,b_j\) 又可和
		\(f_{i-1,j-1}\) 对应的公共子序列构成新的公共子序列
		
		\(\therefore f_{i,j} += 1 + f_{i-1,j-1}\)\\
		\(f[i][j] = \begin{cases} \\ \end{cases}\)\(\left\{\begin{cases}\\ f[i - 1][j]+f[i][j-1]+1 & a_i = b_j\\ f[i - 1][j]+f[i][j - 1]-f[i-1][j-1] & \mathrm{a}_{i} \neq b_{j}\end{cases}\right.\)
		\item
		最长公共子序列个数：
		
		非种类数\\
		定义 \(f_{i,j}\) 表示 \(a\) 的前 \(i\) 位，\(b\) 的前 \(j\)
		位的最长公共子序列个数\\
		\(dp_{i,j}\) 表示 \(a\) 的前 \(i\) 位，\(b\) 的前 \(j\)
		位的最长公共子序列\\
		\(dp_{i,j}\) 可由 \(dp_{i-1,j-1},dp_{i-1,j},dp_{i,j-1}\)
		转移得到，那么：
		
		\begin{enumerate}
			\def\labelenumi{\arabic{enumi}.}
			\item
			当 \(a_i=b_j\)，\(dp_{i,j}\) 必然是由 \(dp_{i-1,j-1}\)
			转移得到，所以 \(f_{i,j} += f_{i-1,j-1}\) ，此时：\\
			如果 \(dp_{i,j} = dp_{i-1,j}\)，那么 \(f_{i,j}+=f_{i-1,j}\)（也说明
			\(dp_{i-1}{j}\) 不是由 \(dp_{i-1,j-1}\)转移得到）如果
			\(dp_{i,j}=dp_{i,j-1}\)，那么 \(f_{i,j} += f_{i,j-1}\)（也说明
			\(dp_{i,j-1}\) 不是由 \(dp_{i-1,j-1}\)转移得到）
			\item
			当 \(a_i \neq b_j\)，\(dp_{i,j}\) 必然是由 \(dp_{i-1,j}\) 或
			\(dp_{i,j-1}\) 转移得到，此时：\\
			如果 \(dp_{i,j} = dp_{i-1,j}\)，那么 \(f_{i,j}+=f_{i-1,j}\)\\
			如果 \(dp_{i,j} = dp_{i,j-1}\)，那么 \(f_{i,j}+=f_{i,j-1}\)\\
			而如果 \(dp_{i,j} = dp_{i-1,j-1}\)，就说明 \(dp_{i-1,j},dp_{i,j-1}\)
			都是由 \(dp_{i-1,j-1}\) 转移得到\\
			那么 \(f_{i,j}\) 就会多计算一次 \(f_{i-1,j-1}\) ，需要减掉这部分贡献
			\item
			初始化 \(f_{i,0} = 1,f_{0,i}=1\)：因为 \(dp_{i,0},dp_{0,i}\) 都等于
			\(0\)，它们的 \(LCS\) 为空集，空集只算一个
		\end{enumerate}
		\item
		公共子序列个数：\\
		种类数\\
		假设求的是三个串（\(A\)、\(B\)、\(C\)）的公共子序列个数：\\
		定义 \(f_{i,j,k}\) 表示 \(a[1...i],b[1...j],c[1...k]\)
		互不相同的公共子序列个数。
		
		\begin{itemize}
			\item
			当 \(a_i=b_j=c_k=ch\) 时，会产生新的公共子序列。此时考虑将 \(ch\)
			接到之前出现的所有公共子序列后，这样就产生了与之前数量相同的新公共子序列，再加上
			\(ch\) 本身，故此时有
			\(f_{i,j,k} = 2\times f_{i-1,j-1,k-1}+1\)。但这样是错的，因为没有考虑重复的情况。\\
			于是可以记录 \(lasta_{{i}},lastb_{{j}},lastc_{{k}}\) 表示 \(ch\)
			在三个字符串中上一次出现的位置，分别记为 \(li,lj,lk\)。那么在计算
			\(f[li][lj][lk]\) 和 \(f[i][j][k]\) 时均会在 \(f[li-1][lj-1][lk-1]\)
			所代表的公共子串末尾接上 \(ch\)。当 \(li,lj,lk\) 均不为 \(0\)
			时，这部分就是重复的，还有 \(ch\) 本身也是重复的，故要考虑去重。
			
			\[f_{i,\,j,\,k} = 2\cdot f_{i-1,\,j-1,\,k-1} - f_{li-1,\,lj-1,\,lk-1}\]
			\item
			若 \(a[i]\)、\(b[j]\)、\(c[k]\)
			不相等，那么没有新的公共子串产生，此时直接将之前的值继承过来即可。但直接复制
			\(f[i-1][j-1][k-1]\) 显然是错的，因为未考虑在 \(f[i-1][j][k]\)
			等处产生的新公共子串。不过很容易可以想到容斥原理：
			
			\(f_{i,\,j,\,k} =f_{i-1,\,j,\,k} + f_{i,\,j-1,\,k} + f_{i,\,j,\,k-1} - f_{i-1,\,j-1,\,k} - f_{i,\,j-1,\,k-1} - f_{i-1,\,j,\,k-1} + f_{i-1,\,j-1,\,k-1}. \)
		\end{itemize}
		\item
	\end{itemize}
	
	\begin{lstlisting}
		// 求最长公共子序列和最长公共子序列的个数
		const int mod = 1e8;
		const int N = 5e3 + 10;
		int f[N][N] , dp[N][N];
		int n , m , a[N] , b[N];
		char s[N] , t[N];
		signed main()
		{
			cin >> s + 1 >> t + 1;
			int n = strlen(s + 1) - 1 , m = strlen(t + 1) - 1;
			for(int i = 1 ; i <= n ; i ++) a[i] = s[i] - 'A';
			for(int i = 1 ; i <= m ; i ++) b[i] = t[i] - 'A';
			int now = 0;
			for(int i = 0 ; i <= max(n , m) ; i ++) f[now][i] = 1;
			for(int i = 1 ; i <= n ; i ++)
			{
				now ^= 1;
				f[now][0] = 1;
				for(int j = 1 ; j <= m ; j ++) f[now][j] = 0 , dp[now][j] = 0;
				for(int j = 1 ; j <= m ; j ++)
				{
					if(a[i] == b[j]) 
					{
						dp[now][j] = dp[now ^ 1][j - 1] + 1;
						f[now][j] += f[now ^ 1][j - 1];
						if(dp[now][j] == dp[now ^ 1][j]) f[now][j] += f[now ^ 1][j];
						if(dp[now][j] == dp[now][j - 1]) f[now][j] += f[now][j - 1];
					}
					else
					{
						dp[now][j] = max(dp[now][j - 1] , dp[now ^ 1][j]);
						if(dp[now][j] == dp[now ^ 1][j]) f[now][j] += f[now ^ 1][j];
						if(dp[now][j] == dp[now][j - 1]) f[now][j] += f[now][j - 1];
						if(dp[now][j] == dp[now ^ 1][j - 1]) f[now][j] -= f[now ^ 1][j - 1];
					}
					f[now][j] = (f[now][j] + mod) % mod;
				}
			}
			cout << dp[now][m] << '\n';
			cout << f[now][m] << '\n';
			return 0;
		}
	\end{lstlisting}
	
	\begin{lstlisting}
		//公共子序列种类数
		const int N = 1e2 + 10;
		char a[N] , b[N] , c[N];
		int lasta[30] , lastb[30] , lastc[30];
		long long f[N][N][N]; 
		signed main()
		{
			cin >> a + 1 >> b + 1 >> c + 1;
			int alen = strlen(a + 1) , blen = strlen(b + 1) , clen = strlen(c + 1);
			for(int i = 1 ; i <= alen ; i ++)
			{
				for(int j = 0 ; j <= 25 ; j ++) lastb[j] = 0;
				for(int j = 1 ; j <= blen ; j ++)
				{
					for(int k = 0 ; k <= 25 ; k ++) lastc[k] = 0;
					for(int k = 1 ; k <= clen ; k ++)
					{
						if(a[i] == b[j] && b[j] == c[k])
						{
							f[i][j][k] = f[i - 1][j - 1][k - 1] * 2 + 1;
							int la = lasta[a[i] - 'a'] , lb = lastb[b[j] - 'a'] , lc = lastc[c[k] - 'a'];
							if(la && lb && lc) f[i][j][k] -= f[la - 1][lb - 1][lc - 1] + 1;
						}
						else
						{
							f[i][j][k] = f[i - 1][j][k] + f[i][j - 1][k] + f[i][j][k - 1]
							- f[i - 1][j - 1][k] - f[i][j - 1][k - 1] - f[i - 1][j][k - 1]
							+ f[i - 1][j - 1][k - 1];
						}
						lastc[c[k] - 'a'] = k;
					}
					lastb[b[j] - 'a'] = j;
				}
				lasta[a[i] - 'a'] = i;
			}
			cout << f[alen][blen][clen] << '\n';
			return 0;
		}
	\end{lstlisting}
	
\end{document}
